ABC 172 D - Sum of Divisors
問題
1からNまでの各整数 k について、(kの約数の個数 * k)を求め、その合計を求めるという問題。
制約
1 < N <= 10^7
回答
解説エントリを見て回るといろいろな解法があるみたいだけど、「約数の個数の表を作る」という解法がシンプルで分かりやすそうなのでこれで考えていく。
まず、愚直に約数の個数の計算をNまでの全ての数に行うととても間に合わない。
code:Kotlin
/**
* 約数列挙
*/
fun enumDivisors(n: Long): List<Long> {
val list = mutableListOf<Long>()
for (i in 1..Math.sqrt(n.toDouble()).toLong()) {
if (n % i == 0L) {
list.add(i)
if (n / i != i) list.add(n / i)
}
}
return list.sorted()
}
そこで出てくるのが「約数の個数の表を作る」という計算方法。
約数の個数だけを考える
約数というのはある値xがyで割り切れる(つまりxがyの倍数である)数のことである。
約数の個数というのはxの中にそのようなyがいくつあるかということだ。
たとえば2の約数は1と2、3の約数は1と3、4の約数は1,2,4である。
(当たり前だと思うかもしれないけど約数の扱いに慣れていないとこれが直感的にイメージ出来ない)
２の約数と３の約数と４の約数にはそれぞれ1が含まれることが分かる。
また、２の約数と４の約数にはそれぞれ２が含まれることも分かる。
もしnが４だったら、１から４までの全ての数の約数に少なくとも１が含まれるので、少なくとも答えは4以上である。
同じように２の約数と４の約数には２が含まれるため、プラス２だ。これで少なくとも答えは4 + 2で6以上であると分かる。
３と４はそれぞれ３の約数と４の約数自身にしか現れないためプラス１ずつして合計は4 + 2 + 1 + 1で8になる。
つまり１から４までの約数の合計は８ということになる！
ここまでをコードに表すと以下のようになると思う。
code:Kotlin
fun problem172d(n: Long): Long {
var ans = 0L
for (i in 1..n) { // 1からNまで
for (j in i..n step i) { // それぞれの整数iの倍数をiからnまで求めてカウントしている
ans++
debugLog(i, j, ans)
}
}
return ans
}
debug： 1, 1, 1
debug： 1, 2, 2
debug： 1, 3, 3
debug： 1, 4, 4
debug： 2, 2, 5
debug： 2, 4, 6
debug： 3, 3, 7
debug： 4, 4, 8
8
約数の個数 * Kを考える
ところで問題は「整数Kの約数の個数の合計」ではなく「整数Kの約数の個数 * Kの合計」であった。
これは一見すると、とても数学的な法則を使って謎の計算をしないと求められなそうに思えるけど、以下のような考え方が出来た。
もう一度約数の内訳を思い出す。
1の約数は1、2の約数は1と2、3の約数は1と3、4の約数は1,2,4である。
これを愚直に考えると以下のようになる。
1 * 1 + 2 * 2 + 3 * 2 + 4 * 3
この中の4 * 3にフォーカスしてみよう。
4 * 3 = 12である。
4の約数には
i = 1, j = 4の1
i = 2, j = 4の1
i = 4, j = 4の1
が含まれる。
この３つのjを合計すると4 * 3と同じく12になる。
なぜかというと、i = 1, j = 4というのは、4の約数に1が含まれるということだからだ。
もっと言えば、iの中にjが登場するということは「jの約数にiが含まれる」という意味だ。
同じように2 * 2の場合を考えてみる。
2 * 2 = 4である。
2の約数には
i = 1, j = 2の1
i = 2, j = 2の1
が含まれる。
この2つのjを合計すると4になる。
これはつまるところ、上に書いたNまでの整数の約数の合計を求めるコードで、jというのはそれを使うKを表しているのだ。
(ちょっと分かりにくいけど、i = 1に対するjがN個あるのを思い出せばイメージしやすいと思う)
よって、先のコードのans++の部分を ans += jに書き換えることによって、約数の個数 * Kを求めることが出来る。
code:Kotlin
fun problem172d(n: Long): Long {
var ans = 0L
for (i in 1..n) {
for (j in i..n step i) {
ans += j
debugLog(i, j, ans)
}
}
return ans
}
debug： 1, 1, 1
debug： 1, 2, 3
debug： 1, 3, 6
debug： 1, 4, 10
debug： 2, 2, 12
debug： 2, 4, 16
debug： 3, 3, 19
debug： 4, 4, 23
もう少しなぜそうなるのかを掘り下げてみたい。
ansにjを足すということは、
4の約数には
i = 1, j = 4の1
i = 2, j = 4の1
i = 4, j = 4の1
が含まれる。
この３つのjを合計すると4 * 3と同じく12になる。
における、jを数え上げていることと同等だからだ。
つまり、1の約数のjと2の約数のjと3の約数のjと...という風に全部足していってしまえば、最終的にはK=4の時に4 + 4 + 4 = 12をやったのと同じことを全てのKに対してやったのと同じことになるというわけ。